https://leetcode.cn/problems/valid-parentheses/
//有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。


示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;//top总是在栈顶的上一位
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
STDataType StackTop(ST* ps)//返回栈顶的数为多少
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool isValid(char* s) {
	ST st;
	StackInit(&st);
	while (*s)
	{
		if ((*s == '(') || (*s == '{') || (*s == '['))
		{
			StackPush(&st, *s);
			s++;
		}
		else
		{
			if (StackEmpty(&st))
			{
				StackDestory(&st);//注意内存泄漏
				return false;//这里解决只有右括号的情况
			}
			STDataType top = StackTop(&st);
			StackPop(&st);
			if ((top == '(') && (*s == ')') || (top == '[') && (*s == ']') || (top == '{') && (*s == '}'))
			{
				s++;
			}
			else
			{
				StackDestory(&st);//这里要注意内存泄漏的问题
				return false;
			}

		}
	}
	bool ret = StackEmpty(&st);//用来解决只有左括号，没有右括号的情况
	StackDestory(&st);
	return ret;
}


https://leetcode.cn/problems/copy-list-with-random-pointer/
//复制带随机指针的链表
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
	while (cur)
	{
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		copy->val = cur->val;
		copy->next = cur->next;
		cur->next = copy;
		cur = copy->next;
	}
	cur = head;
	while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = copy->next;

	}
	cur = head;
	struct Node* copyhead = NULL;
	struct Node* copytail = NULL;
	while (cur)
	{
		//尾插
		struct Node* copy = cur->next;
		struct Node* next = copy->next;
		if (copytail == NULL)
		{
			copyhead = copytail = copy;
		}
		else
		{
			copytail->next = copy;
			copytail = copytail->next;
		}
		cur->next = next;
		cur = next;
	}
	return copyhead;
}